#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <iostream>
using namespace std;
#define ll long long
const int N = 1e6+5;
#define clr(a) memset(a, 0, sizeof(a))
ll K;
int Sqr,zhi[N],pri[N],sp[N],tot,m,id1[N],id2[N],g[N],h[N];
ll n,w[N];
void Sieve(int n){
    zhi[1]=1;
    for (int i=2;i<=n;++i){
        if (!zhi[i]) pri[++tot]=i,sp[tot]=(sp[tot-1]+i)%K;
        for (int j=1;i*pri[j]<=n;++j){
            zhi[i*pri[j]]=1;
            if (i%pri[j]==0) break;
        }
    }
}
inline void up(ll &a, ll b) {a = a+b>K? a+b-K:a+b;}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T; cin >> T;
    while (T--){
        tot = m = 0;
        cin >> n >> K;
        ++n;
        Sqr=sqrt(n);Sieve(Sqr);
        for (ll i=1,j;i<=n;i=j+1){
            j=n/(n/i);w[++m]=n/i;
            if (w[m]<=Sqr) id1[w[m]]=m;
            else id2[n/w[m]]=m;
//            h[m]=(w[m]-1)%K;
            g[m]=((w[m]+2)%K)*((w[m]-1)%K)%K;
            if (g[m]&1) g[m]+=K;g[m]/=2;
        }
        for (int j=1;j<=tot;++j)
            for (int i=1;i<=m&&1ll*pri[j]*pri[j]<=w[i];++i){
                int k=(w[i]/pri[j]<=Sqr)?id1[w[i]/pri[j]]:id2[n/(w[i]/pri[j])];
                g[i]=(g[i]-1ll*pri[j]*(g[k]-sp[j-1])%K)%K;
                g[i] = g[i]<0? g[i]+K:g[i];
//                g[i]=(g[i]+K)%K;
//                h[i]=(h[i]-h[k]+j-1 + K)%K;
            }
        ll t = (((n+2)%K) * (n-1)%K)%K * (K+1)/2%K;
        up(t, g[1]-4);
        cout << t << "\n";
    }

    return 0;
}